#给你两棵二叉树： root1 和 root2 。想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。返回合并后的二叉树。
#注意: 合并过程必须从两个树的根节点开始。
class TreeNode:
    """
    LeetCode官方TreeNode类仿写（模拟官方功能）
    主要用于本地IDE调试
    """
    def __init__(self, val):
        if isinstance(val, list):
            if len(val) == 0:
                self.val = None
            else:
                self.val = val[0]
        elif isinstance(val, int) or isinstance(val, str):
            self.val = val
        self.left = None
        self.right = None

    def gatherAttrs(self):
        return ", ".join("{}: {}".format(k, getattr(self, k)) for k in self.__dict__.keys())

    def __str__(self):
        return self.__class__.__name__ + "{" + "{}".format(self.gatherAttrs()) + "}"
def build_TreeNode(val):
    if val is None:
        return None
    elif isinstance(val, list):
        if len(val) == 0:
            return None
        else:
            head = TreeNode(val[0])
            wait_node_list = [head]
            left = False
            for i in range(1, len(val)):
                node = TreeNode(val[i])
                if not left:
                    if val[i] is not None:
                        wait_node_list[0].left = node
                        wait_node_list.append(node)
                    left = True
                else:
                    if val[i] is not None:
                        wait_node_list[0].right = node
                        wait_node_list.append(node)
                    left = False
                    wait_node_list.pop(0)
            return head
    elif isinstance(val, int) or isinstance(val, str):
        return TreeNode(val)
    else:
        return None
###############################################################################################
class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if not t1:
            return t2
        if not t2:
            return t1       
        merged = TreeNode(t1.val + t2.val)
        merged.left = self.mergeTrees(t1.left, t2.left)
        merged.right = self.mergeTrees(t1.right, t2.right)
        return merged